package sword.chapter2Array;

import java.util.HashMap;

/**
 * 0和1个数相同的子数组
 * 输入一个只包含0和1的数组，请问如何求最长0和1的个数相同的连续子数组的长度？
 * 例如在数组[0, 1, 0]中有两个子数组包含相同个数的0和1，分别是[0, 1]和[1, 0]，它们的长度都是2，因此输出2。
 * <p>
 * 累加数组
 * 1. 记录第一次Si的下标位置
 * 2. 0替换成-1，变成求和等于0
 *
 * @author K
 * @date 2021-11-03 8:35
 */
public class S11FindMaxLength {
    public static void main(String[] args) {
        int[] nums = new int[]{0, 1, 0, 1};
        int result = findMaxLength(nums);
        System.out.println();
    }

    public static int findMaxLength(int[] nums) {
        int sum = 0;
        int maxLength = 0;
        HashMap<Integer, Integer> map = new HashMap<>();
        // 0出现的位置是-1 {0,1,0,1}=> 0{0,1,0,1} 0在最左边-1位置
        map.put(0, -1);
        for (int i = 0; i < nums.length; i++) {
            // 当前Si
            sum += nums[i] == 0 ? -1 : 1;
            if (map.containsKey(sum)) {
                // Sj（历史的Si） Si=Sj Si-Sj=0，取历史Si的下标，计算i-j得到数组长度
                maxLength = Math.max(maxLength, i - map.get(sum));
            } else {
                // 存放Si的下标值
                map.put(sum, i);
            }
        }
        return maxLength;
    }
}
